package com.zhupf.graph;

import java.util.*;

/**
 * @author zhupf
 * @date 2023年12月19日 16:27
 * @Description 你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
 * <p>
 * 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。
 * <p>
 * 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
 * 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：numCourses = 2, prerequisites = [[1,0]]
 * 输出：true
 * 解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
 * 示例 2：
 * <p>
 * 输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
 * 输出：false
 * 解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
 */
public class CanFinish {

    private LinkedList<Integer>[] graph;

    private int[] inDegree;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        graph = new LinkedList[numCourses];
        inDegree = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new LinkedList<>();
        }
        for (int[] prerequisite : prerequisites) {
            graph[prerequisite[1]].add(prerequisite[0]);
            inDegree[prerequisite[0]]++;
        }
        Stack<Integer> stk = new Stack<>();
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < inDegree.length; i++) {
            if (inDegree[i] == 0) {
                stk.push(i);
            }
        }
        while (!stk.isEmpty()) {
            Integer i = stk.pop();
            res.add(i);
            for (Integer idx : graph[i]) {
                if ((--inDegree[idx]) == 0) {
                    stk.push(idx);
                }

            }
        }
        return numCourses == res.size();
    }


    private List<List<Integer>> edges;
    private int[] visited;
    private boolean res;

    public boolean canFinish2(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<>();
        visited = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            edges.add(i, new ArrayList<>());
        }
        for (int[] prerequisite : prerequisites) {
            edges.get(prerequisite[1]).add(prerequisite[0]);
        }
        res = true;
        for (int i = 0; i < edges.size() && res; i++) {
            if (visited[i] == 0) {
                dfs(i);
            }
        }
        return res;
    }

    private void dfs(int i) {
        visited[i] = 1;
        for (Integer integer : edges.get(i)) {
            if (visited[integer] == 0){
                dfs(integer);
                if(!res){
                    return;
                }
            }else if(visited[integer] == 1){
                res = false;
                return;
            }
        }
        visited[i] = 2;
    }


    public int[] findOrder(int numCourses, int[][] prerequisites) {
        graph = new LinkedList[numCourses];
        inDegree = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new LinkedList<>();
        }
        for (int[] prerequisite : prerequisites) {
            graph[prerequisite[1]].add(prerequisite[0]);
            inDegree[prerequisite[0]]++;
        }
        Stack<Integer> stk = new Stack<>();
        int[] res = new int[numCourses];
        for (int i = 0; i < inDegree.length; i++) {
            if (inDegree[i] == 0) {
                stk.push(i);
            }
        }
        int idxx = 0;
        int sss = 0;
        while (!stk.isEmpty()) {
            Integer i = stk.pop();
            res[idxx++] = i;
            sss++;
            for (Integer idx : graph[i]) {
                if ((--inDegree[idx]) == 0) {
                    stk.push(idx);
                }

            }
        }
        if (sss != numCourses) {
            return new int[0];
        }
        return res;

    }

}
